//
//  Problem1252.swift
//  TestProject
//
//  Created by 武侠 on 2021/4/13.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1252. 奇数值单元格的数目
 给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

 另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

 对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

 ri 行上的所有单元格，加 1 。
 ci 列上的所有单元格，加 1 。
 给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。

 示例 1：
     输入：m = 2, n = 3, indices = [[0,1],[1,1]]
     输出：6
     解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
     第一次增量操作后得到 [[1,2,1],[0,1,0]]。
     最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。
 示例 2：
     输入：m = 2, n = 2, indices = [[1,1],[0,0]]
     输出：0
     解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
 提示：
     1 <= m, n <= 50
     1 <= indices.length <= 100
     0 <= ri < m
     0 <= ci < n
 进阶：你可以设计一个时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题吗？
 */
@objcMembers class Problem1252: NSObject {
    func solution() {
        print(oddCellsClear(2, 3, [[0,1],[1,1]]))
        
        print(oddCellsClear(2, 2, [[1,1],[0,0]]))
    }
    
    /*
     1: 创建一个数组rows记录每一行的增加的个数   奇数 = 1 偶数 = 0
     2: 创建一个数组colums记录每一列的增加的个数 奇数 = 1 偶数 = 0
     3: 那么indeices[i][j] = rows[i] + coluns[j]
     */
    func oddCells(_ m: Int, _ n: Int, _ indices: [[Int]]) -> Int {
        var rows = Array(repeating: 0, count: m)
        var colums = Array(repeating: 0, count: n)
        
        var result = 0
        for indice in indices {
            rows[indice[0]] = rows[indice[0]] == 0 ? 1 : 0
            colums[indice[1]] = colums[indice[1]]  == 0 ? 1 : 0
        }
        print(rows)
        print(colums)
        for i in 0..<m {
            for j in 0..<n {
                if rows[i] + colums[j] == 1 {
                    result += 1
                }
            }
        }
        
        return result
    }
    
    /*
     进一步优化： -: 奇数 +：偶数
     行：
     ------------
     ------------
     ------------
     ++++++++++++
     ++++++++++++
     ++++++++++++
     
     列：
     ----++++++++
     ----++++++++
     ----++++++++
     ----++++++++
     ----++++++++
     ----++++++++
     
     合并的话: 左上角（1+1 = 2）和右下角都是偶数，那么只要计算出：右上+左下
     ....--------
     ....--------
     ....--------
     ----++++++++
     ----++++++++
     ----++++++++
     */
    func oddCellsClear(_ m: Int, _ n: Int, _ indices: [[Int]]) -> Int {
        var rows = Array(repeating: 0, count: m)
        var colums = Array(repeating: 0, count: n)
        
        
        for ind in indices  {
            rows[ind[0]] = rows[ind[0]] == 0 ? 1 : 0
            colums[ind[1]] = colums[ind[1]] == 0 ? 1 : 0
        }
        
        var rowSum = 0
        for i in rows {
            rowSum += i
        }
        var colSum = 0
        for j in colums {
            colSum += j
        }
        // 右上 + 左下
        return rowSum * (n - colSum) + colSum * (m - rowSum)
    }
}
